Preferential Attachment with Flexible Heavy Tails

Thomas Boughen
t.w.boughen1@newcastle.ac.uk

Newcastle Univeristy

Clement Lee
Clement.Lee@newcastle.ac.uk

Newcastle Univeristy

Vianey Palacios Ramirez
vianey.palacios-ramirez@newcastle.ac.uk

Newcastle Univeristy

June 23, 2025

Areas of Focus

Mechanistic Models

  • e.g. Forest fire, preferential attachment (PA) , duplication divergence
  • Model behaviour of individual nodes and edges over time

Degree Distributions

  • e.g. Power Laws, tail estimation, mixture models
  • Model feature of a network structure, usually at a snapshot in time

Mechanistic Models

Preferential Attachment

Steps

  1. Node added to network
  2. Connects to existing nodes with weights \(\pi_i\): \[ \pi_i\propto b(k_i), \] where \(k_i\) is degree of node \(i\).

Preference Function

\[ \begin{gather} b(k) = k^\alpha \end{gather} \]

\(0\le\alpha<1\) : not scale-free network

\(0\le\alpha<1\) : scale-free network

\(0\le\alpha<1\) : “winner takes all”

Mechanistic Models

+

  • Can achieve complex behaviour with simple rules
  • Can gain insight into individual behaviour
  • If able to fit, can create predictions for network growth

-

  • Can be hard to fit, full evolution often not available

Modelling Degrees

Power Law

Tail Estimation

Mixture Model

Mixture Model [1]

Zipf-Polylog until threshold

\[ f(k) \propto x^{-\alpha} \theta^x, \qquad x=1, 2, \ldots, u \]

Discrete Generalised Pareto after

\[ f(k)\propto 1-\left(1+\frac{\xi(k-u)}{\sigma +\xi u}\right)_+^{-1/\xi}, \qquad x=u+1, u+2,\ldots \]

Modelling Degrees

+

  • Easy to fit
  • Learn about (in)equality between nodes

-

  • Learn nothing about network growth
  • Degrees aren’t everything

Returning to Preferential Attachment

Propose preference function of the form:

\[ b(k) = \begin{cases} k^\alpha + \varepsilon, &k\le k_0,\\ (k_0^\alpha + \varepsilon) + \beta(k-k_0), &k\ge k_0. \end{cases} \]

Limiting Degree Distribution [2]

\[ \bar F(k) = \prod_{i=0}^k\frac{b(i)}{\lambda^* + b(i)},\qquad k=0,1,2,\ldots \]

  • Heavy-tailed for all parameter choices

  • Allows sub/super-linear behaviour

  • Tail over \(k_0\) approximately discrete GP

Fitting Simulated Data

  • Networks simulated with 100,000 nodes

  • Various parameter choices

  • Seems to recover parameters from degrees alone

Real Data

[description of data sets, add icon so can be easily tracked to next slides]

  1. as-caida

  2. open-flights

  3. reactome

Fitting to Real Data

[show posterior survival and mixture model and data on sample plot]

Bonus Information

[show posterior preference functions, not obtained normally when modelling degrees]

Summary

[presented a model for degree distributions that may shed light on how a network grew, using a preference function that generates realistic tail behaviour]

[theory used is for trees, so the bonus information may only really applicable for tree-like networks]

Thank you for listening!

Contacts

Thomas Boughen*

(t.w.boughen1@ncl.ac.uk)

Clement Lee

(Clement.Lee@ncl.ac.uk)

Vianey Palacios Ramirez

(vianey.palacios-ramirez@ncl.ac.uk)

References

1.
Lee C, Eastoe EF, Farrell A (2024) Degree distributions in networks: Beyond the power law. Statistica Neerlandica 78(4):702–718. https://doi.org/https://doi.org/10.1111/stan.12355
2.
Rudas A, Tóth B, Valkó B (2007) Random trees and general branching processes. Random Structures & Algorithms 31(2):186–202. https://doi.org/https://doi.org/10.1002/rsa.20137